package com.study.indusry;

/**
 * 快速排序
 * 总结：快速排序就是 递归+区分 我们的基准值就是用来区分数据的。左取值和右取值都是我们对应的改变，随机取值和其他的取值也是对快速排序的一些优化，其核心还是没变
 */
public class QuickSort {
    public static void main(String[] args){
//        int[] arr = {1,3,2,4,5,8,6,7,9,1};
        int[] arr = {1,3,2,4,5,8,6,7,8,9};
        QuickSort quickSort = new QuickSort();
        //左右指针理解版
//        quickSort.quickSort(0,arr.length-1,arr);
        //左指针优化版
//        quickSort.quickSortLift(0,arr.length-1,arr);
        //右指针优化版
//        quickSort.quickSortRight(0,arr.length-1,arr);
        //填坑法
//        quickSort.quickSortFillPit(0,arr.length-1,arr);
        //指针法
        quickSort.quickSortDobIndex(0,arr.length-1,arr);
    }

    //左右排序
    public void quickSort(int low, int end, int[] arr){
        //当数组为空或为一个数的时候返回
        if(low >= end){
            return;
        }
        //设置左指针
        int i = low;
        //设置右指针
        int j = end;
        //设置基准值
        int temp = arr[low];
        //循环，使得基准数左边的数小于它右边的数大于它
        while(j>i){
            while(arr[j]>=temp && j>i){
                j--;
            }
            //带上 = 是为了不让数与基准值相等时还要交换，&&i<j 这个条件是 若基准值刚好是数组中的最大最小值的时候，防止数组越界
            while(arr[i]<=temp && i<j){
                i++;
            }
            int k = arr[i];
            arr[i] = arr[j];
            arr[j] = k;
        }
        arr[low] = arr[i];
        arr[i] = temp;
        printF(arr);
        quickSort(low,i-1, arr);
        quickSort(i+1, end, arr);
    }
    //左基准值排序优化
    public void quickSortLift(int low, int end, int[] arr){
        if(low >= end){
            return;
        }
        int i = low;
        //这儿+1是因为待会要--j
        int j = end+1;
        while(j>i){
            //左基准值，要先从右往左扫，这样才不会避免判断基准值是最大或最小值
            // （因为 j>i 若先从左往右则无法发判断数列中最后一个非基准值与基准值的大小就直接交换数据了）
            // ，同理右基准值，需要先从左往右扫
            while(arr[--j] >= arr[low] && j > i){}
            while(arr[++i] <= arr[low] && j > i){}
            //因为++i之后，就有可能i指针在j指针之后，加上 j>i 的判断这样就可以防止 i在j之后的数据交换了
            if(j > i) {
                int k = arr[i];
                arr[i] = arr[j];
                arr[j] = k;
            }
        }
        //交换
        exchangeNum(low,j,arr);//这儿就是：谁是先扫描的指针，就用其与基准数交换
        printF(arr);
        quickSortLift(low,j-1,arr);
        quickSortLift(j+1,end,arr);
    }
    //右基准值优化版
    public void quickSortRight(int low, int end, int[]arr){
        if(low>=end){
            return;
        }
        int i=low-1;
        int j=end;
        while (j>i){
            while (arr[++i] <= arr[end] && j>i){};
            while (arr[--j] >= arr[end] && j>i){};
            if(j > i) {
                exchangeNum(i, j, arr);
            }
        }
        exchangeNum(i,end,arr);
        printF(arr);
        quickSortRight(low, i-1, arr);
        quickSortRight(i+1, end, arr);
    }
    //填坑法
    public void quickSortFillPit(int low, int end, int[] arr){
        if(low >= end){
            return;
        }
        int i = low;
        int j = end;
        //把基准数从数组里拔出来，此时low指向的数据就相当于是一个坑
        int temp = arr[low];
        //开始循环扫描
        while(j > i){
            //取最左边的值就是要从最右边扫
            while(arr[j]>=temp && j>i){
                j--;
            }
            //此时有小于基准数的数就放到坑里面，放入之后，现在坑就是j指向的数据中
            arr[i] = arr[j];
            printF(arr);
            while(arr[i]<=temp && j>i){
                i++;
            }
            //这是把大于基准数的数据放入j指向的坑中，现在坑右变成了i
            arr[j] = arr[i];
            printF(arr);
        }
        //当i == j的时候循环就跳出来了，这时就把基准数放入坑中
        arr[i] = temp;
        printF(arr);
        quickSortFillPit(low, i-1,arr);
        quickSortFillPit(i+1,end,arr);
    }
    //前后针法
    public void quickSortDobIndex(int low, int end, int[] arr){
        if(low >= end){
            return;
        }
        int i = low;
        int j = i;
        int temp = arr[low];
        while (i<end){
            if(arr[++i] < temp){
                exchangeNum(i,j,arr);
                j++;
            }
        }
        arr[j] = temp;
        printF(arr);
        quickSortDobIndex(low,j-1,arr);
        quickSortDobIndex(j+1,end,arr);
    }

    public void printF(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.printf(arr[i]+",");
        }
        System.out.println();
    }

    public static void exchangeNum(int a, int b, int[]arr){
        int k = arr[b];
        arr[b] = arr[a];
        arr[a] = k;
    }
}

